The present invention relates to an address generating apparatus and a motion vector detecting apparatus and, more particularly, to an improved address generation mechanism to perform data memory access which is employed for reading/writing image data by a digital signal processor for image processing or the like, and an image data controlling apparatus which performs motion vector detection employing that mechanism.
In a signal processor handling image data and the like, an address generating apparatus which generates addresses of a two-dimensional rectangular area is employed as an address generating apparatus which can efficiently access a data memory
This is because, while, for example, data arranged two dimensionally such as image data should be mapped in one-dimensional address space when they are to be stored into a memory, and generally, image data are generally mapped in one-dimensional addresses in the order in which the image data are raster scanned, in a case where these data are handled as two-dimensional data, a rectangular area is often cut out to be used.
As an address generating apparatus which generalizes this kind of address generating apparatus, there is one disclosed in Japanese Published Patent Application No. Hei. 4-218847, which can access to a multidimensional area in data memory, the configuration of which is illustrated in FIG. 18.
In FIG. 18, numerals 901-1 through 901-N denote incremental value setting means in first through Nth scanning directions, respectively, numeral 902 denotes a first multiplexer which selects one of the outputs of the incremental value setting means in the first scanning direction 901-1 through the incremental value setting means in the Nth scanning direction 901-N to output the same, numeral 903 denotes a start address setting means which sets an start address, numerals 904-1 through 904-N denote first through Nth cumulative registers which correspond to the first through Nth scanning directions, respectively, numeral 905 denotes a second multiplexer which selects one of the outputs of the first cumulative register 904-1 through Nth cumulative register 904-N to output the same, numeral 906 denotes an adder which adds the output of the first multiplexer 902 and the output of the second multiplexer 905, numeral 907 denotes a third multiplexer which selects one of the outputs of the adder 906 and the start address setting means 903 to output the same, numerals 908-1 through 908-N denote data number setting means in the first scanning direction through the Nth scanning direction, respectively, and numeral 909 denotes a control circuit which generates a control signal based on set values of the data number setting means 908-1 in the first scanning direction through the data setting means 908-N in the Nth scanning direction.
The multidimensional address generating apparatus configured as described above has the output of the first cumulative register 904-1 as an output address.
FIG. 19 is one having simplified the multidimensional address generating apparatus in FIG. 18 so that it can generate a two-dimensional address, and hereinafter, the operation of the multidimensional address generating apparatus in FIG. 18 will be described as referring to a case where a two-dimensional address is generated by this conventional two-dimensional address generating apparatus, for simplification.
First, suppose that a rectangular area of arbitrary P1xc3x97P2 (P1 and P2 are natural numbers such as 16 and 16, for example) is an access object. Initially, at 0th cycle, start address data SA is set to the first cumulative register 904-1 and the second cumulative register 904-2 as an initial value by a start address data setting device 903.
At a subsequent first cycle, data of the first cumulative register 904-1 and incremental data DX in the first scanning direction (direction X) are added by the adder 906 and the addition result is written into the first cumulative register 904-1, so as to generate an address immediately after the initial value. The writing is not performed to the second cumulative register 904-2. Subsequently, the same operation as that at the first cycle is performed from second cycle to P1xe2x88x921th cycle to continue writing.
Next, at P1th cycle, data of the second cumulative register 904-2 and incremental data DY in the second scanning direction (direction Y) are added by the adder 906 and the addition result is written into both of the first cumulative register 904-1 and the second cumulative register 904-2.
Similarly, every other cycle from P1+1th cycle to 2P1xe2x88x921th cycle, . . . , from (P2xe2x88x921) P1+1th cycle to P2xc2x7P1xe2x88x921th cycle, a control is performed so that the data of the first cumulative register 904-1 and the incremental data DX in the first scanning direction are added by the adder 906 and the result is written into the first cumulative register 904-1, and at every P1 cycle of P1th cycle, 2P1th cycle, . . . , (P2xe2x88x921) P1th cycle, a control is performed so that the data of the second cumulative register 904-2 and the incremental data DY in the second scanning direction are added and the result is written into the first cumulative register 904-1 and the second cumulative register 904-2, thereby outputting a value of the first cumulative register 904-1 obtained as a result of carrying out the 0th cycle to the P2xc2x7P1xe2x88x921th cycle as an address.
A data flow due to such operation will be described in FIG. 20. An initial address of a subsequent line is calculated employing an initial address of a previous row or column stored in the second cumulative register 904-2 as shown in FIG. 20.
An example of the control circuit 909 in FIG. 19 will be described in FIG. 21. In FIG. 21, numeral 909-1 denotes a first counter, an initial value of which is P1, and which repeats the operation of starting a count from 1 to sequentially increment to P1 according to a clock, numeral 909-3 denotes a second counter, an initial value of which is P2, and which repeats the operation of starting a count from 1 to sequentially increment to P2 according to a clock, numeral 909-2 denotes a data P1, numeral 909-4 denotes a data P2, numeral 909-11 denotes a data P1-1, numerals 909-5 and 909-8 denote AND circuits, numerals 909-6, 909-7, and 909-12 denote comparators which compare two data to output 1 when they match and to output 0 when they do not match, numerals 909-9, 909-10, and 909-13 denote D flipflops, numeral 909-14 denotes a first clock, numeral 909-15 denotes a second clock, numeral 909-16 denotes a control signal, and numeral 909-17 denotes an END signal.
The control circuit in FIG. 21 operates at a timing in FIG. 20. The control signal 909-16 is employed as a first control signal 29-1 and a second control signal 29-2 in figure 19, the first clock 909-14 is employed as a writing signal 29-4, and the second clock 909-15 is employed as a second writing signal 29-5, thereby performing a control following a timing chart in FIG. 22.
A third control signal 29-3 of a third multiplexer 917 in FIG. 19 performs a control so that a start address data of the start address data setting device 903 is selected at the activation of a two-dimensional address generating apparatus (at a 0th cycle), while an output address of the adder 906 is selected at other cycles.
An example of a state where actual image data are accessed will be described in FIG. 23. FIG. 23(a) is a schematic diagram illustrating an access in a lateral direction and FIG. 23(b) is a schematic diagram illustrating an access in a longitudinal direction.
First, the operation when an access is performed in a lateral direction will be described with reference to FIG. 23(a). Numeral 61 denotes a whole image data composed of a rectangular area of 6xc3x977 pixels, and numeral 62 denotes an objective rectangular area to be accessed of 4xc3x974 pixels. 0 to 41 denote actual addresses of a memory, and (0) to (15) represent an order of accessing the objective rectangular area to be accessed of 4xc3x974 pixels out of addresses of the whole image data of 6xc3x977 pixels. In this case, 1 is set as the incremental data DX in the first scanning direction and the data number 6 in a line is set as the incremental data DY in the second scanning direction.
At 0th cycle, 7 is written into the first cumulative register 904-1 and the second cumulative register 904-2 as the start address data SA. At each cycle from a first cycle to a third cycle, the incremental data DX in the first scanning direction (1 in this example) is sequentially added to the value 7 of the first cumulative register 904-1 to write the result thereinto, thereby generating addresses 8, 9, and 10.
At a fourth cycle, the incremental data DY in the second scanning direction (6 in this example) is added to the address 7 held in the second cumulative register 904-2 to write the result into the first cumulative register 904-1 and the second cumulative register 904-2, thereby generating an address 13. At each cycle from a fifth cycle to a seventh cycle, 1 is sequentially added to the value 13 of the first cumulative register 904-1 as the incremental data DX in the first scanning direction to write into the first cumulative register 904-1, thereby generating addresses 14, 15, and 16.
At an eighth cycle, 6 is added to the value 13 of the second cumulative register 904-2 as the incremental data in the second scanning direction to write the result into the first cumulative register 904-1 and the second cumulative register 904-2, thereby generating an address 19.
Hereinafter, addresses 20, 21, 25, 26, 27, and 28 are generated sequentially in the same way, thereby realizing an access of the objective rectangular area 62 to be accessed in the whole image data 61.
Next, the operation when an access is performed in a longitudinal direction will be described with reference to FIG. 23(b). Numeral 63 denotes a whole image data composed of a rectangular area of 6xc3x977 pixels, and numeral 64 denotes an objective rectangular area to be accessed of 4xc3x974 pixels. 0 to 41 denote actual addresses of a memory, and (0) to (15) represent an order of accessing.
In this case, 6 is set as the incremental data DX in the first scanning direction and the data number 1 in a line is set as the incremental data DY in the second scanning direction.
At 0th cycle, the value 7 is written into the first cumulative register 904-1 and the second cumulative register 904-2 as the start address data SA. At each cycle from a first cycle to a third cycle, the incremental data DX in the first scanning direction (6 in this example) is sequentially added to the value 7 of the first cumulative register 904-1 to write the result into the first cumulative register 904-1 and the second cumulative register 904-2. At each cycle from a first cycle to a third cycle, the incremental data DX in the first scanning direction (6 in this example) is sequentially added to the value 7 of the first cumulative register 904-1 to write the result thereinto, thereby generating addresses 13, 19, and 25.
At a fourth cycle, the incremental data DY in the second scanning direction (1 in this example) is added to the address 7 held in the second cumulative register 904-2 to write the result into the first cumulative register 904-1 and the second cumulative register 904-2, thereby generating an address 8. At each cycle from a fifth cycle to a seventh cycle, the incremental data in the first scanning direction 6 is sequentially added to the value of the first cumulative register 904-1 to write the result into the first cumulative register 904-1, thereby generating addresses 14, 20, and 26.
At an eighth cycle, 1 is added to the value 8 of the second cumulative register 904-2 as the incremental data in the second scanning direction to write the result into the first cumulative register 904-1 and the second cumulative register 904-2, thereby generating an address 9.
Hereinafter, addresses 15, 21, 27, 10, 16, 22, and 28 are generated sequentially in the same way, thereby realizing an access of the objective rectangular area 64 to be accessed in the whole image data 63.
As described above, when the access direction is to be changed toward the identical objective rectangular area 62 or 64 to be accessed, it is only required to replace the incremental data DX in the first scanning direction and the incremental data DY in the second scanning direction with each other. Further, by changing one or both of the incremental data in the first scanning direction and the incremental data in the second scanning direction, it is also possible to access a parallel body area or to access with jumping. When accessing a multidimensional space, a multidimensional parallelism area is accessed.
Meanwhile, in a case where data are subjected to DMA transfer from an external memory to a smaller amount data memory inside a processor to be stored therein, when the whole area of the external memory is attempted to be referred to, an area corresponding to the data memory should he scrolled, and this requires to perform DMA transfer of data corresponding to the amount of data memory each time. The amount of the data memory and the number of DMA transfer are in trade-off relationship, and there is a problem that when the amount of the data memory is to be reduced, the number of DMA transfer increases, and inversely, when the number of DMA transfer is to be reduced, the amount of the data memory increases.
Further, there is an image CODEC as an example of the image processing as described above, which is performed by an image processing apparatus having an address generating apparatus, and in an algorithm of the image CODEC, ME (motion vector detection) processing is generally employed. This ME processing comprises performing comparison of a luminance value of a 16xc3x9716-pixel image block (macro block; hereinafter referred to as MB) out of input images with a luminance value of a time-wise previous image employing an evaluation function of SAD (sum of absolute difference), and retrieving the most approximate image position, thereby obtaining the displacement. AS a kind of retrieval algorithm to perform the ME processing in a programmable way, there is xe2x80x9cOne at a timexe2x80x9d algorithm.
In the xe2x80x9cOne at a timexe2x80x9d algorithm, SAD calculation is performed with respect to eight adjacent macro blocks, which are shifted by pixels to left, right, up, down, diagonally to the upper right, diagonally to the lower right, diagonally to the upper left, and diagonally to the lower left, respectively from a retrieval origin as a comparison object (a macro block which has a starting point at an upper left corner of a rectangular memory area is a retrieval origin), and when there exist blocks that provide smaller SAD values than the SAD value of the retrieval origin, a macro block that provides the smallest SAD value thereamong is a new retrieval origin, and the same retrieval is repeated Until all the SAD values of the adjacent eight macro blocks are larger than or equal to the retrieval origin, thereby obtaining a motion vector.
When an algorithm such as that of the above-described xe2x80x9cone at a timexe2x80x9d is to be processed by a processor which is equipped with the conventional address generating apparatus described in FIG. 18, one is employed, as a method of locating pixel data for retrieving in a data memory, which comprises locating all the pixel data existing in a range to which retrieval could reach in the data memory at once and accessing a macro block of 16xc3x9716 pixels by a means for generating address in a two-dimensional area, thereby to perform retrieving. However, in a case where the maximal number of retrieval set by a user is, for example, 40 times, a pixel number required when retrieval reaches the maximal number of retrieval is 96xc3x9796 pixels, resulting in a problem that a large area which the processor directly uses is occupied in the data memory.
Further, as one which can reduce the amount of a memory corresponding to the data memory, there is a graphic display scroll device as disclosed in Japanese Published Patent Application No. Hei. 8-202524.
As shown in FIG. 25, when a display screen DS to be scrolled is to run over a display data area DA, this graphic display scroll device divides an area that is to run over by extension lines of the boundaries of the display data area DA, draws out these using area corresponding to areas in the display data area DA which are not used for storing the display screen DS, and reads out these, thereby enabling a smooth scroll even when the display data area DA is reduced to four of display screens DS, and resulting in a further reduction of the memory amount with relative to the above-mentioned method.
However, this prior art, attempts, when the display screen DS is to run over the display data area DA horizontally, for example, to the right side to move the running over area to the left-side area corresponding in the display data area DA, and in order to realize this horizontal movement, a judgement as to whether it runs over horizontally or not, or an arithmetic operations for address correction is required, resulting in an increase in the circuit scale or an increase in the processing time of a CPU. In addition, it is necessary for the display screen DS to be present in the display data area DA at first, and an area to run over is restricted to a two-dimensional rectangular area.
Further, when the retrieval range goes beyond a specific area determined by a user due to a movement of the retrieval origin in a case where an area in the data memory which is occupied by the ME processing is restricted to a searching range that is less than the maximal retrieval number, pixels which are newly required should be supplied by a DMA transfer. However, in order to perform a block access by a conventional two-dimensional address generating means, it is necessary to transfer all the search range including pixels newly required, thereby resulting in an increased transfer number at the DMA transfer.
The present invention is made to solve the above-mentioned problems of the conventional ones and has for its object to provide an address generating apparatus which can automatically generate an address of a multidimensional area which does not run over a restricted area in the data memory which is set by a user, needs fewer DMA transfer number, can solve a contradictory problem that the DMA transfer number should increase when an increase in the data memory area is suppressed, while the data memory area should increase when an increase in the DMA transfer number is suppressed, and can suppress an increase in the data memory area will neither increasing the circuit scale or CPU processing, nor restricting the existing position and configuration at the beginning of the running over area.
Further, it is an object of the present invention to provide an address generating apparatus with variety, which is not specialized only to the addressing for ME processing, as an address generating apparatus of a processor.
Further, it is an object of the present invention to provide a motion vector detector which, by employing such an address generating apparatus, can automatically generate an address in the multidimensional area, can solve the contradictory problem of an increase in the data memory area and an increase in the DMA transfer number, and can suppress an increase in the data memory area without causing an increase in the circuit scale or an increase in the CPU processing, thereby achieving an effect with respect to a motion vector detection processing.
To solve the above-described problems, according to claim 1 of the present invention, there is provided an address generating apparatus which comprises: an addressing domain setting means for setting a successive addressing area which is determined by a top address and a final address, the top address having a value smaller than that of the final address; a multidimensional address generating means which can successively generate addresses in a multidimensional area; a first comparing means for comparing respective addresses subsequently generated by the multidimensional address generating means with the final address; a second comparing means for comparing respective addresses subsequently generated by the multidimensional address generating means with the top address; and an address correction means for receiving the respective addresses subsequently generated by the multidimensional address generating means and the comparison results of the first and second comparing means as inputs, judging whether or not the respective addresses subsequently generated by the multidimensional address generating means should run over the addressing domain set by the addressing domain setting means, based on the comparison results of the first and second comparing means, and correcting the respective addresses so that they are located in a spiral annular space in the addressing domain to output the result when they run over, and outputting addresses of a subsequent cycle as they are when they do not run over.
According to this address generating apparatus, when a user sets an addressing domain in the memory where the top address shows a value smaller than that of the final address, addresses running over the addressing domain are corrected into the corresponding addresses in the addressing domain when the addressing domain is supposed to be a spiral annular space so as to be output, even when an addressing area set in the multidimensional address generating means includes outside of the addressing domain, thereby an automatic generation of addresses in the multidimensional area which do not run over a restricted area in the data memory set by a user can be realized, by a hardware, solving an contradictory problem of an increase in the data memory area and an increase in the DMA transfer number, and suppressing an increase in the data memory area without causing an increase in the circuit scale and in the CPU processing.
According to claim 2 of the invention, there is provided an address generating apparatus which comprises: an addressing domain setting means for setting a successive addressing area which is determined by a top address and a final address, regardless whether the value of the top address and the final address is large or small; a multidimensional address generating means which can successively generate addresses in a multidimensional area; a first comparing means for comparing respective addresses subsequently generated by the multidimensional address generating means with the final address; a second comparing means for comparing respective addresses subsequently generated by the multidimensional address generating means with the top address; an address detecting means for detecting to which of the top address and the final address, the address of a subsequent cycle is nearer based on the comparison result of the first comparing means and the comparison result of the second comparing means; and an address correction means for receiving the comparison results of the first and second comparing means, the output of the address detecting means, and the address of a subsequent cycle as inputs, judging whether or not the respective addresses subsequently generated by the multidimensional address generating means should run over the addressing domain set by the addressing domain setting means, based on the comparison results of the first and second comparing means and the output of the address detection means, and, correcting the respective addresses so that they are located in a spiral annular space in the addressing domain to output the result when they run over, while outputting addresses of a subsequent cycle as they are when they do not run over.
According to this address generating apparatus, in addition to that the address generation is realized as by the address generating apparatus of claim 1, there is no restriction, regarding the memory area which can be set as the addressing domain, that the top address must have a value smaller than that of the final value, thereby enabling setting of the addressing domain that strides the memory area, in which the top address shows a value larger than that of the final address, and solving a contradictory problem of an increase in the data memory area or in the DMA transfer number.
According to claim 3 of the invention, in the address generating apparatus as defined in claim 1 or 2, the addressing domain setting means is configured such that the addressing domain sets the final address and the total data number, and the top address is automatically generated by subtracting the total data number from the final address.
Therefore, in addition to that the reduction in the address generation is realized as by the address generating apparatus of claim 1 or 2, a correction calculation in the address correction means is simplified, resulting in reduction of the circuit scale.
According to claim 4 of the present invention, there is provided an address generating apparatus as defined in claim 1 or 2, wherein the multidimensional address generating means which can successively generate addresses in a multidimensional area comprises a means for setting a start address in a multidimensional area, incremental values in respective scanning directions, and data numbers in respective scanning directions and an independent cumulative register for accumulating addresses in respective scanning directions, and calculates an address value of a subsequent cycle by adding the incremental value corresponding to the scanning direction to the cumulative register corresponding to the scanning direction at an address calculation when the scanning direction is changed, to output the same, and updates the start address in the multidimensional area at a start cycle of addressing by the output of the address correction means.
Therefore, in addition to that the address generation is realized as by the address generating apparatus of in claim 1 or 2, in a case where the start address of a multidimensional space to be accessed is already outside the addressing domain, and thus an actual memory access is preformed with an address that is obtained by correcting the start address, the start address setting means is automatically set again to the corrected address employed for the actual access, whereby the amount of arithmetic operations required for address calculations by a program when a new addressing is performed based on the start address is reduced.
According to claim 5 of the invention, there is provided an address generating apparatus as defined in claim 1 or 2, wherein the multidimensional address generating means which can successively generate addresses in a multidimensional area comprises a data number setting means for setting a start address in a multidimensional area, incremental values in respective scanning directions, and data numbers in respective scanning directions and an independent cumulative register for accumulating addresses in respective scanning directions, and calculates an address value of a subsequent cycle by adding the incremental value corresponding to the scanning direction to the cumulative register corresponding to the scanning direction at an address calculation when the scanning direction is changed, to output the same, and among the cumulative registers for accumulating the addresses in respective scanning directions, a cumulative register in the lowest order scanning direction stores a corrected address outputted by the address correction means, while the other cumulative register stores one selected from the corrected address outputted by the address correction means and the address value of a subsequent cycle, and the output of the cumulative register storing an address in the lowest scanning direction is taken out as an output address.
With such configuration, in addition to that the address generation as by the address generating apparatus of claim 1 or 2, the corrected addresses are stored in the cumulative registers in respective scanning directions of the multidimensional address generating means, whereby the addresses of a subsequent cycle outputted at the successive accessing by the multidimensional address generating means do not indicate addresses in an area which can not be corrected by the address correction means.
According to claim 6 of the present invention, there is provided an address generating apparatus as defined claim 5, the addressing domain setting means is configured such that the addressing domain sets the final address and the total data number, and the top address is automatically generated by subtracting the total data number from the final address.
Therefore, in addition to that the address generation realized by the address generating apparatus of claim 5, a correction calculation in the address correction means is simplified, and the circuit scale is reduced.
According to claim 7 of the invention, there is provided an address generating apparatus as defined in claim 5, wherein the multidimensional address generating means generates a start address of the multidimensional area which is updated by the address output at a start cycle of addressing.
Therefore, in addition to that the address generation is realized as by the address generating apparatus of claim 5 in a case where the start address of a multidimensional area to be accessed is already outside the addressing domain, and thus an actual memory access is preformed with an address obtained by correcting the start address, the start address setting means is automatically set again to the corrected address employed for the actual access, whereby the amount of arithmetic operations required for address calculations by a program when a new addressing is performed based on the start address is reduced.
According to claim 8 of the invention, there is provided an address generating apparatus as defined in claim 1 or 2, wherein the multidimensional address generating means which can successively generate addresses in a multidimensional area comprises a data number setting means for setting a start address in a multidimensional area, incremental values in respective scanning directions, and data numbers in respective scanning directions and an independent cumulative register for accumulating addresses in respective scanning directions, and calculates an address value of a subsequent cycle by adding the incremental value corresponding to the scanning direction to the cumulative register corresponding to the scanning direction an address calculation when the scanning direction is changed, to output the same, and among the cumulative registers for accumulating the addresses in respective scanning directions, a cumulative register in the lowest order scanning direction stores the address value of a subsequent cycle while other cumulative register stores one selected from the corrected addresses outputted by the address correction means and the address value of a subsequent cycle, and one selected from the output of the cumulative register storing an address in the lowest scanning direction and the address outputted by an address pointer of the address correcting means is taken out as an output address.
With such configuration, in addition to that the address generation is realized by the address generating apparatus of claim 1 or 2, a regular address generation by the multidimensional address generating means and an address generation in which a multidimensional address is generated without running over the addressing domain can be realized in a same circuit by switching a mode switching signal:
According to claim 9 of the invention, there is provided an address generating apparatus as defined in claim 8, wherein the addressing domain setting means is configured such that the addressing domain sets the final address and the total data number, and the top address is automatically generated by subtracting the total data number from the final address.
Therefore, in addition to that the address generation is realized as by the address generating apparatus of claim 8, a correction calculation in the address correcting means is simplified, and the circuit scale is reduced.
According to claim 10 of the present invention, there is provided an address generating apparatus as defined in claim 8, wherein the start address of the multidimensional area is updated by the address output at a start cycle of addressing.
Therefore, in addition to that the address generation is realized by the address generating apparatus of claim 8, in a case where the start address of a multidimensional area to be accessed is already outside the addressing domain, and thus an actual memory access is preformed with an address that is obtained by correcting the start address, the start address setting means is automatically set again to the corrected address employed for the actual access, whereby the amount of arithmetic operations required for address calculations by a program when a new addressing is performed based on the start address is reduced.
According to claim 11 of the present invention, there is provided a motion vector detector which comprises: a memory outside a processor for storing image data; an internal memory inside a processor for storing image data used for arithmetic operations for the motion vector detection only, employing direct memory access transfer from the memory outside the processor; an arithmetic means for performing arithmetic operations for the motion vector detection; and an address generating apparatus as defined in any of claims 1 to 10 which generates an address for to accessing a rectangular area of the internal memory.
With such configuration, with respect to image data required for motion vector detection, there is no necessity for arranging all the data in a range where search is to be performed in the internal memory, and it is possible to take only the pixels that are required as searching processing goes on into the internal memory. This is effective for the motion vector detection processing in a small sized terminal having only limited memory capacity, and provides effects on the DMA transfer of the minimum required amount and the suppression of address calculation of a memory.